#include <bits/stdc++.h>
using namespace std;
class Solution
{
  private:
    // 定义记忆化数组为类的成员变量
    vector<vector<int>> memo;

    // 深度优先搜索函数
    int dfs_memo(vector<vector<int>> &matrix, int i, int j)
    {
        // 如果记忆化数组中已经有结果，直接返回
        if (memo[i][j] != 0)
            return memo[i][j];
        int max_len = 1;
        // 定义四个方向：上、下、左、右
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (auto &dir : dirs)
        {
            int x = i + dir[0], y = j + dir[1];
            // 检查新坐标是否合法且满足递增条件
            if (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size() &&
                matrix[i][j] < matrix[x][y])
            {
                // 更新最大长度
                max_len = max(max_len, 1 + dfs_memo(matrix, x, y));
            }
        }
        // 将结果存入记忆化数组
        memo[i][j] = max_len;
        return max_len;
    }

  public:
    int solve(vector<vector<int>> &matrix)
    {
        if (matrix.empty())
            return 0;
        // 初始化记忆化数组
        memo = vector<vector<int>>(matrix.size(),
                                   vector<int>(matrix[0].size(), 0));
        int max_len = 0;
        // 遍历矩阵的每个元素
        for (int i = 0; i < matrix.size(); ++i)
        {
            for (int j = 0; j < matrix[0].size(); ++j)
            {
                // 更新最大长度
                max_len = max(max_len, dfs_memo(matrix, i, j));
            }
        }
        return max_len;
    }
};

class Solution
{
  private:
    int dfs(vector<vector<int>> &matrix, int i, int j)
    {
        int maxLength = 1;
        int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        for (auto &dir : dirs)
        {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x >= 0 && x < matrix.size() - 1 && y >= 0 &&
                y < matrix[0].size() - 1 && matrix[x][y] > matrix[i][j])
                maxLength = max(maxLength, 1 + dfs(matrix, x, y));
        }
        return maxLength;
    }

  public:
    int solve(vector<vector<int>> &matrix)
    {
        if (matrix.empty())
        {
            return 0;
        }
        int maxLength = 0;
        for (int i = 0; i < matrix.size(); i++)
        {
            for (int j = 0; j < matrix[0].size(); j++)
            {
                maxLength = max(maxLength, dfs(matrix, i, j));
            }
        }
        return maxLength;
    }
};




class Solution
{
  public:
    int solve(vector<vector<int>> &matrix)
    {
        if (matrix.empty())
            return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<vector<int>> dp(n, vector<int>(m, 1));
        vector<tuple<int, int, int>> cells;

        // 收集所有格子并排序
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j)
                cells.emplace_back(matrix[i][j], i, j);
        sort(cells.begin(), cells.end());

        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int max_len = 1;

        for (auto &cell : cells)
        {
            int i = get<1>(cell), j = get<2>(cell);
            for (auto &dir : dirs)
            {
                int x = i + dir[0], y = j + dir[1];
                if (x >= 0 && x < n && y >= 0 && y < m &&
                    matrix[x][y] < matrix[i][j])
                {
                    dp[i][j] = max(dp[i][j], dp[x][y] + 1);
                }
            }
            max_len = max(max_len, dp[i][j]);
        }
        return max_len;
    }
};